/*
 * Copyright (c) 2019. Lorem ipsum dolor sit amet, consectetur adipiscing elit.
 * Morbi non lorem porttitor neque feugiat blandit. Ut vitae ipsum eget quam lacinia accumsan.
 * Etiam sed turpis ac ipsum condimentum fringilla. Maecenas magna.
 * Proin dapibus sapien vel ante. Aliquam erat volutpat. Pellentesque sagittis ligula eget metus.
 * Vestibulum commodo. Ut rhoncus gravida arcu.
 */

package com.darly.std.math;

import com.darly.dlcommon.common.dlog.DLog;

import java.util.Random;

/**
 * Description TODO: 计算题
 * Package com.darly.std.math
 *
 * @author zhangyuhui
 * Date 2019/7/25 14:44

 */
public class MathLib {

    /**
     * 已知 sqrt (2)约等于 1.414，要求不用数学库，求 sqrt (2)精确到小数点后 10 位。
     * 出题人：——阿里巴巴出题专家：文景／阿里云 CDN 资深技术专家
     * 牛顿迭代法:  y = (x + c / x) / 2;
     * 实际上求的结果是曲线和X轴交接的地方
     *
     * @param cons 输入参数
     * @return 返回结果（无限趋近的算法）
     */
    public static double sqrt(double cons) {
        if (cons < 0) {
            return Double.NaN;
        }
        double per = cons;
        double next = (per + per / cons) / 2;
        double lead = 1e-15;
        while (Math.abs(per - next) > lead) {
            per = next;
            next = (per + per / cons) / 2;
        }
        return per;
    }


    /**
     * a、冒泡排序，是通过每一次遍历获取最大/最小值
     * b、将最大值/最小值放在尾部/头部
     * c、然后除开最大值/最小值，剩下的数据在进行遍历获取最大/最小值
     */
    public static void On2(int arr[],boolean isTest){
        long start = System.currentTimeMillis();
        DLog.d("[冒泡排序开始]");
        //冒泡
        for (int i = 0; i < arr.length; i++) {
            //外层循环，遍历次数
            if (isTest){
                DLog.d(sout(arr));
            }
            for (int j = 0; j < arr.length - i - 1; j++) {
                //内层循环，升序（如果前一个值比后一个值大，则交换）
                //内层循环一次，获取一个最大值
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        DLog.d("[冒泡排序耗时]"+(System.currentTimeMillis() - start));
        DLog.d("[冒泡排序结束]");
    }

    /**
     * a、选择排序,将第一个值看成最小值
     * b、然后和后续的比较找出最小值和下标
     * c、交换本次遍历的起始值和最小值
     * d、说明：每次遍历的时候，将前面找出的最小值，看成一个有序的列表，后面的看成无序的列表，然后每次遍历无序列表找出最小值。
     */
    public static void SelectOn2(int arr[],boolean isTest){
        long start = System.currentTimeMillis();
        DLog.d("[选择排序开始]");
        //选择
        for (int i = 0; i < arr.length; i++) {
            if (isTest){
                DLog.d(sout(arr));
            }
            //默认第一个是最小的。
            int min = arr[i];
            //记录最小的下标
            int index = i;
            //通过与后面的数据进行比较得出，最小值和下标
            for (int j = i + 1; j < arr.length; j++) {
                if (min > arr[j]) {
                    min = arr[j];
                    index = j;
                }
            }
            //然后将最小值与本次循环的，开始值交换
            int temp = arr[i];
            arr[i] = min;
            arr[index] = temp;
            //说明：将i前面的数据看成一个排好的队列，i后面的看成一个无序队列。每次只需要找无需的最小值，做替换
        }
        DLog.d("[选择排序耗时]"+(System.currentTimeMillis() - start));
        DLog.d("[选择排序结束]");
    }

    /**
     * a、插入排序,默认从第二个数据开始比较。
     * b、如果第二个数据比第一个小，则交换。然后在用第三个数据比较，如果比前面小，则插入（狡猾）。否则，退出循环
     * c、说明：默认将第一数据看成有序列表，后面无序的列表循环每一个数据，如果比前面的数据小则插入（交换）。否则退出。
     */
    public static void InsertOn2(int arr[],boolean isTest){
        long start = System.currentTimeMillis();
        DLog.d("[插入排序开始]");
        //插入排序
        for (int i = 1; i < arr.length; i++) {
            if (isTest){
                DLog.d(sout(arr));
            }
            //外层循环，从第二个开始比较
            for (int j = i; j > 0; j--) {
                //内存循环，与前面排好序的数据比较，如果后面的数据小于前面的则交换
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                } else {
                    //如果不小于，说明插入完毕，退出内层循环
                    break;
                }
            }
        }
        DLog.d("[插入排序耗时]"+(System.currentTimeMillis() - start));
        DLog.d("[插入排序结束]");
    }

    /**
     * 希尔排序（插入排序变种版）
     * a、基本上和插入排序一样的道理
     * b、不一样的地方在于，每次循环的步长，通过减半的方式来实现
     * c、说明：基本原理和插入排序类似，不一样的地方在于。通过间隔多个数据来进行插入排序。
     */
    public static void ThorOnLogN(int arr[],boolean isTest){
        long start = System.currentTimeMillis();
        DLog.d("[希尔排序开始]");
        //希尔排序（插入排序变种版）
        for (int i = arr.length / 2; i > 0; i /= 2) {
            if (isTest){
                DLog.d(sout(arr));
            }
            //i层循环控制步长
            for (int j = i; j < arr.length; j++) {
                //j控制无序端的起始位置
                for (int k = j; k > 0  && k - i >= 0; k -= i) {
                    if (arr[k] < arr[k - i]) {
                        int temp = arr[k - i];
                        arr[k - i] = arr[k];
                        arr[k] = temp;
                    } else {
                        break;
                    }
                }
            }
            //j,k为插入排序，不过步长为i
        }
        DLog.d("[希尔排序耗时]"+(System.currentTimeMillis() - start));
        DLog.d("[希尔排序结束]");
    }


    private static String sout(int key[]){
        StringBuilder value = new StringBuilder();
        value.append("[");
        for (int i:key) {
            value.append(i);
            value.append(",");
        }
        value.deleteCharAt(value.length()-1);
        value.append("]");
        return value.toString();
    }
}
